#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MVNum 100
typedef enum { FALSE, TRUE } Boolean;

typedef char VerTexType;      
typedef int ArcType;          

typedef struct {
    VerTexType vexs[MVNum];     
    ArcType arcs[MVNum][MVNum]; 
    int vexnum, arcnum;         
} MGraph;

int locate_vertex(MGraph* G, char vertex_name) {
    for (int i = 0; i < G->vexnum; ++i) {
        if (vertex_name == G->vexs[i]) {
            return i;
        }
    }
    return -1;
}

void create_graph(MGraph** G_pp, char* graph_data_filename)
{
    FILE* fp;
    size_t len = 0;
    ssize_t read;

    int num_nodes, num_edges;
    *G_pp = (MGraph*)malloc(sizeof(MGraph));
    if (*G_pp == NULL) {
        printf("ʼʧ");
    }
    fp = fopen(graph_data_filename, "r");
    if (fp == NULL)
    {
        printf("ʧ");
        exit(EXIT_FAILURE);
    }
    fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
    for (int i = 0; i < num_nodes; ++i) {
        fscanf(fp, "%c\n", &((*G_pp)->vexs[i]));
    }
    (*G_pp)->vexnum = num_nodes;
    (*G_pp)->arcnum = num_edges;
    for (int i = 0; i < num_edges; ++i) {
        char j, k;
        fscanf(fp, "%c %c\n", &j, &k);
        int a = locate_vertex(*G_pp, j), b = locate_vertex(*G_pp, k);
        (*G_pp)->arcs[a][b] = 1;
        (*G_pp)->arcs[b][a] = 1;
    }
    fclose(fp);
}

void dfs(MGraph* G, int i, Boolean visited[], char* result_sequence, int* visited_order)
{
    visited[i] = TRUE;
    char* s;
    s = (char*)malloc(2);
    s[0] = G->vexs[i];
    s[1] = '\0';
    *visited_order = G->vexs[i];
    strcat(result_sequence, s);
    for (int j = 0; j < G->vexnum; j++) {
        if (G->arcs[i][j] == 1 && visited[j] == FALSE) {
            dfs(G, j, visited, result_sequence, visited_order);
        }
    }
}

void bfs(MGraph* G, int k, Boolean visited[], char* visited_sequence)
{
    char* s;
    s = (char*)malloc(2);
    s[0] = G->vexs[k];
    s[1] = '\0';
    visited[k] = TRUE;
    strcat(visited_sequence, s);
    char str = *visited_sequence;
    int i = 0;
    while (str != '\0') {
        for (int j = 0; j < G->vexnum; j++) {
            if (G->arcs[k][j] == 1 && visited[j] == FALSE) {
                visited[j] = TRUE;
                char* s;
                s = (char*)malloc(2);
                s[0] = G->vexs[j];
                s[1] = '\0';
                strcat(visited_sequence, s);
            }
        }
        i++;
        str = *(visited_sequence + i);
        if (str != '\0')
            k = locate_vertex(G, str);
    }
}

int main() {
    int i;
    MGraph* G;
    Boolean visited[MVNum];

    create_graph(&G, "graph_data.txt"); 
    for (i = 0; i < MVNum; i++) {
        visited[i] = FALSE;
    }
    char dfs_sequence[MVNum] = { '\0' };
    int visited_order = 0;
    dfs(G, 0, visited, dfs_sequence, &visited_order);
    printf("Print Graph DFS: ");
    printf("%s\n", dfs_sequence);
    printf("\n");


    for (i = 0; i < MVNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence[MVNum] = { '\0' };
    bfs(G, 0, visited, bfs_sequence); 
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence);
    printf("\n");
    for (i = 0; i < MVNum; i++) {
        visited[i] = FALSE;
    }
    char bfs_sequence2[MVNum] = { '\0' };
    bfs(G, 3, visited, bfs_sequence2); 
    printf("Print Graph BFS: ");
    printf("%s\n", bfs_sequence2);
    printf("\n");
    return 0;
}